/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

/**
 * @author : sunzb
 * @date: 2019/5/16
 */
public class _29_509_Fibonacci {

    private int[] memo;

    public static int dt(int n) {
        if (n < 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public _29_509_Fibonacci(int n) {
        memo = new int[n + 1];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = i == 0 ? 0 : i == 1 ? 1 : -1;
        }
    }

    public int dg(int n) {
        return n == 0 ? 0 : n == 1 ? 1 : dg(n - 1) + dg(n - 2);
    }

    public int dg1(int n) {
        int value = memo[n];
        if (value != -1) return value;
        memo[n] = dg1(n - 1) + dg1(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        System.out.println(new _29_509_Fibonacci(5).dg(5));
        System.out.println(new _29_509_Fibonacci(5).dg1(5));
        System.out.println(dt(5));
    }
}
